#include <vector>
#include <string>
#include <list>
#include <sstream>
#include <iostream>
#include <cstdlib>
//using namespace std;
class Cell{
	private:
		int row;
		int col;
		double val;
		int ref_count;
		std::vector<std::string> express;
		std::list<int> dep;
	public:
		Cell(){
			this->row = 0;
			this->col = 0;
			this->val = 0;
			this->ref_count = 0;
		}
		void set_position(int row, int col){
			this->row = row;
			this->col = col;
		}
		double get_val(){
			return this->val;
		}
		int get_ref_count(){
			return this->ref_count;	
		}
		void set_express(std::string exprs, Cell cellMap[], int num_col){
			std::istringstream iss (exprs);
			std::string temp;
			while(iss >> temp && temp != ""){
				this->express.push_back(temp);
				if(temp[0] >= 'A' && temp[0] <= 'Z'){
					this->ref_count++;
					int temp_row = temp[0] - 'A';
					int temp_col = atoi((temp.substr(1)).c_str())-1;
					cellMap[temp_row*num_col+temp_col].dep.push_back(this->row*num_col+this->col);
				}					
			}
		}
		bool decRefcountIsZero(){
			this->ref_count--;
			return (this->ref_count == 0);	
		}
		void remove_dep(Cell cellMap[], std::queue<int> &solveList){
			while(!dep.empty()){
				int cand = this->dep.front();
				this->dep.pop_front();
				if(cellMap[cand].decRefcountIsZero()){
					solveList.push(cand);
				}
			}	
		}
		void compute(Cell cellMap[], int num_col){
			this->val = evalRPN(this->express, cellMap, num_col);
		}
		
	private:
		bool is_number(std::string str){
			if(str.length()==0){
				return false;
			}
			switch(str[0]){
				case '+':
				case '-':
				case '*':
				case '/':return false;
				default: break;
			}
			return true;
    	}
    	double convert_num(std::string str, Cell cellMap[], int num_col){
			if(str[0] >= 'A' && str[0] <= 'Z'){
				int row = str[0]-'A';
				int col = std::atoi((str.substr(1)).c_str())-1;
				return cellMap[row*num_col+col].get_val();
			}else{
				return std::atof(str.c_str());
			}
    	}
    	std::string convert_string(double num){
       		std::string result;
			std::stringstream ss;
			ss << num;
			result = ss.str();
			return result;
    	}
		typedef struct{
			int next;
			int prev;
		}node;
    	double evalRPN(std::vector<std::string> &tokens, Cell map[], int num_col) {
        	if(tokens.size()==1){
	            return convert_num(tokens[0], map, num_col);
	        }
			node index_list[tokens.size()];
			for(unsigned i=0; i<tokens.size(); i++){
				index_list[i].prev = i-1;
				index_list[i].next = i+1;
			}
			int itf = 0;
	        int its = 1;
	        unsigned ito = 2;
			double result;
			while(ito < tokens.size()){
	        
	        	while(tokens[ito] != "+" && tokens[ito] != "-"
					&& tokens[ito] != "*" && tokens[ito] != "/"){
	            	ito = index_list[ito].next;
	        	}
    	    	its = index_list[ito].prev;
				while(!is_number(tokens[its])){
					its = index_list[its].prev;
				}
				itf = index_list[its].prev;
				while(!is_number(tokens[itf])){
					itf = index_list[itf].prev;
				}
	        	double f = convert_num(tokens[itf], map, num_col);
	       	 	double s = convert_num(tokens[its], map, num_col);
	       		if(tokens[ito] == "+"){
	       	     	result = f + s;
	       	 	}else if(tokens[ito] == "-"){
	            	result = f - s;
	        	}else if(tokens[ito] == "*"){
	            	result = f * s;
	        	}else if(tokens[ito] == "/"){
	            	result = f / s;
	        	}
	        	tokens[itf] = "";
				index_list[index_list[itf].prev].next = index_list[itf].next;
				index_list[index_list[itf].next].prev = index_list[itf].prev;
				tokens[its] = "";
				index_list[index_list[its].prev].next = index_list[its].next;
				index_list[index_list[its].next].prev = index_list[its].prev;
		        tokens[ito] = convert_string(result);
		
				ito = index_list[ito].next;
			}
	        return result;
	    }
};
